package srcInterviewPrep;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class UglyNumber 
{
    public static int[] GetFirstKUglyNumbers(int k)
    {
        // Argument validations
        
        int[] nums = new int[k];
        
        nums[0] = 1;
        
        Queue<Integer> q2 = new LinkedList<Integer>();
        q2.add(2);
        
        Queue<Integer> q3 = new LinkedList<Integer>();
        q3.add(3);
        
        Queue<Integer> q5 = new LinkedList<Integer>();
        q5.add(5);
        
        for (int i = 1; i < k; ++i)
        {
            int v2 = !q2.isEmpty() ? q2.peek() : Integer.MAX_VALUE;
            int v3 = !q3.isEmpty() ? q3.peek() : Integer.MAX_VALUE;
            int v5 = !q5.isEmpty() ? q5.peek() : Integer.MAX_VALUE;
            
            int v = Math.min(v2, Math.min(v3, v5));
            
            if (v == v2)
            {
                q2.remove();
                q2.add(v*2);
                q3.add(v*3);
                q5.add(v*5);
            }
            else if (v == v3)
            {
                q3.remove();
                q3.add(v*3);
                q5.add(v*5);
            }
            else
            {
                q5.remove();
                q5.add(v*5);
            }
            
            nums[i] = v;
        }
        
        return nums;
    }
    
    public static int[] getNthUglyNo(int n)
    {
        int[] ugly = new int [n];
        
        int i2 = 0, i3 = 0, i5 = 0;
        int i;
        int next_multiple_of_2 = 2;
        int next_multiple_of_3 = 3;
        int next_multiple_of_5 = 5;
        int next_ugly_no = 1;
        ugly[0] = 1;
     
        for(i=1; i<n; i++)
        {
           next_ugly_no = min(next_multiple_of_2,
                               next_multiple_of_3,
                               next_multiple_of_5);
           ugly[i] = next_ugly_no;
           
           if(next_ugly_no == next_multiple_of_2)
           {
               i2 = i2+1;       
               next_multiple_of_2 = ugly[i2]*2;
           }
           if(next_ugly_no == next_multiple_of_3)
           {
               i3 = i3+1;
               next_multiple_of_3 = ugly[i3]*3;
           }
           if(next_ugly_no == next_multiple_of_5)
           {
               i5 = i5+1;
               next_multiple_of_5 = ugly[i5]*5;
           }
        } /*End of for loop (i=1; i<n; i++) */
        return ugly;
    }
     
    /* Function to find minimum of 3 numbers */
    static int min(int a, int b, int c)
    {
        if(a <= b)
        {
          if(a <= c)
            return a;
          else
            return c;
        }
        if(b <= c)
          return b;
        else
          return c;
    }
}
